package 滑动窗口;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 串联所有单词的子串
 * 给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 
 * words 中所有单词串联形成的子串的起始位置。
 * 注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，
 * 但不需要考虑 words 中单词串联的顺序。
 * <p>
 * 输入：s = "barfoothefoobarman", words = ["foo","bar"]
 * 输出：[0,9]
 * 解释：
 * 从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
 * 输出的顺序不重要, [9,0] 也是有效答案。
 */
public class LeetCode30 {
    public static void main(String[] args) {
        String s = "barfoothefoobarman";
        String[] words = {"foo", "bar"};
        List result = findSubstring(s, words);
        System.out.println(result);
    }

    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        // 单次数量
        int wordNum = words.length;
        if (wordNum == 0) {
            return res;
        }
        // 每个单词长度
        int wordLen = words[0].length();
        // hashMap1 存所有单词,以及它出现的次数
        HashMap<String, Integer> allWords = new HashMap<>();
        for (String word : words) {
            Integer val = allWords.getOrDefault(word, 0);
            allWords.put(word, val + 1);
        }
        // 遍历所有的字串
        for (int i = 0; i < s.length() - wordLen * wordNum + 1; i++) {
            // hashMap2 存当前扫描的单词所含有的单词
            HashMap<String, Integer> hasWords = new HashMap<>();
            int num = 0;
            while (num < wordNum) {
                String word = s.substring(i + num * wordLen, i + (num + 1) * wordLen);
                // 判断该单词是否在hashMap1中
                if (allWords.containsKey(word)) {
                    Integer value = hasWords.getOrDefault(word, 0);
                    hasWords.put(word, value + 1);
                    // 判断当前单词的value 和 hashMap1 中该单词的value
                    if (hasWords.get(word) > allWords.get(word)) {
                        break; // 不可能相同，直接进去下一个循环
                    }
                } else {
                    break;
                }
                num++;
            }
            // 判断是不是所有的单词都符合条件
            if (num == wordNum) {
                res.add(i);
            }
        }
        return res;
    }
}
